#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : coins.py
@Time    : 2022/11/06 19:02:35
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 找零问题
"""


def zhao_ling(coin_value_ls: list, change: int, known_ret: list) -> int:
    min_coins = change
    if change in coin_value_ls:  # 递归结束条件
        known_ret[change] = 1  # 记录最优解
        return 1
    elif known_ret[change] > 0:  # 查表成功，直接使用最优解
        return known_ret[change]
    else:
        for m in [c for c in coin_value_ls if c <= change]:
            num_coins = 1 + zhao_ling(coin_value_ls, change - m, known_ret)
            if num_coins < min_coins:
                min_coins = num_coins
                # 找到最优解，记录到表中
                known_ret[change] = min_coins

    return min_coins


def dp_zhao_ling(
    coin_value_ls: list, change: int, min_coins: list, coin_used: list
) -> int:
    """找零的动态规划解法
    Args:
        coin_value_ls (list): 面值列表
        change (int): 需要找零的数目
        min_coins (list): 找零最小数目列表
        coin_used (list): 添加的最优解
    Returns:
        int: 最小方案的货币数量
    """
    # 从1分开始到change逐个计算硬币数
    for cents in range(1, change + 1):
        coin_cnt = cents  # 初始一个最大值，全是1分的
        new_coin = 1  # 初始化一下新加硬币

        # 减去每个硬币，向后查最少硬币数，同时计录总的最少数
        for m in [c for c in coin_value_ls if c <= cents]:
            if min_coins[cents - m] + 1 < coin_cnt:
                coin_cnt = min_coins[cents - m] + 1
                new_coin = m  # 对应最小数量

        min_coins[cents] = coin_cnt  # 得到当前的最少硬币数，记录到列表中
        coin_used[cents] = new_coin  # 记录本步骤加的1个硬币
    # 返回最后一个结果
    return min_coins[change]


def print_coins(coin_uesd: list, change: int):
    print("change %d used:" % change)
    coin = change
    while coin > 0:
        this_coin = coin_uesd[coin]
        print(this_coin, end=" ")
        coin = coin - this_coin
    print("")
